The present invention relates generally to the field of content addressable memories (CAMs) and particularly to a circuit and method for providing a highest priority binary memory match line address resulting from a search operation.
A content addressable memory (CAM) is a binary or ternary memory storage device in which data is searched, read and written based on the content of the stored data, rather than the location where the data is stored. Each CAM memory cell is created by the intersection of a row and an associated match line and a column and associated search line. A CAM typically compares externally-provided search data with stored data in each row of the CAM array and provides match results on multiple match lines. The match results are subsequently provided to a priority encoder which converts the match results into a binary address representing the highest priority matching address. Each match line provides a xe2x80x9chitxe2x80x9d or xe2x80x9cmatchxe2x80x9d indication if the stored data word matches the search word and provides a xe2x80x9cmissxe2x80x9d or xe2x80x9cmis-matchxe2x80x9d indication if the stored data does not match the search word. Each row and match line combination has a unique N-bit address within the CAM. Accordingly, for any search cycle there may be up to 2N match lines activated. Using the N-bit address generated by the priority encoder, the CAM may provide the address as an output for applications such as IP routing table lookup, compression and decompression.
Usually within the context of CAM array, the highest priority matching word is located at the lowest physical address in the CAM array and, accordingly, the lowest priority matching word is located at the highest physical address in the CAM array.
It may be well appreciated that a complex array of standard static boolean logic gates is required to achieve this function. This problem is further complicated by a requirement to deliver address information at a full data rate of the search-and-compare function of the CAM. The most difficult logic operation that a priority encoder must perform is to detect the highest priority match line and to disable any and all lower priority match lines at a high speed. Once the single highest priority match line output has been resolved, a programmable logic array (PLA) or read-only-memory memory (ROM) is used to convert the highest priority match line output into a binary address. The function of detecting the highest priority match line and disabling all lower priority match lines is conventionally implemented using an array of standard boolean logic gates. Examples of such approaches are proposed by Yamagata et al. in IEEE publication xe2x80x9cA 288-kb Fully Parallel Content Addressable Memory Using a Stacked Capacitor Cell Structurexe2x80x9d, IEEE Journal of Solid State Circuits Vol. 27, No. 12, December 1992 pp. 1927-1933 and by Shultz et al. in IEEE publication xe2x80x9cFully Parallel Integrated CAM/RAM Using Preclassification to Enable Large Capacities,xe2x80x9d IEEE Journal of Solid State Circuits Vol. 31, No. 5, May 1996. However, the resulting static logic gate implementations are relatively complex and consume large areas of semiconductor as well as introduce substantial propagation delays. Accordingly, there is a need for an efficient high-speed priority encoder for resolving a highest priority match which exhibits reduced circuit complexity and area consumed.
In accordance with an aspect of the present invention there is provided a circuit for selecting a highest priority signal from a plurality of input signals. The circuit comprises the following components. A plurality of serially coupled input blocks, each of which are coupled to a corresponding one of a plurality of input lines for receiving respective ones of the input signals and providing corresponding output signals. A pre-charging device coupled between a first supply voltage terminal and a first one of the serially coupled input blocks. The pre-charging device couples the supply voltage to the first one of the serially coupled input blocks in response to a clock pulse signal transition. An activation device coupled between a second supply voltage terminal and a last one of the serially coupled input blocks. The activation device couples the second supply voltage to the last one of the serially coupled input blocks in response to an activation signal transition. The second supply voltage is propagated through the plurality of input blocks to an input block having an input signal voltage that is different from a predefined voltage state. The second supply voltage terminal is subsequently provided as the only output from said plurality of input blocks representing a highest priority match signal.